﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ArraysAndStrings.FindDiagonalOrder
{
    class MainProject
    {
        static void Main(string[] args)
        {
            int[][] nums = new int[][]
            {
                //new int[] { 1,2,3,4 } ,
                //new int[] { 5,6,7,8 } ,
                //new int[] { 9,10,11,12 } ,
                //new int[] { 13,14,15,16} ,
                new int[] { 6,9,7} ,
            };
            int[] arr = FindDiagonalOrder(nums);
            foreach (var item in arr)
            {
                Console.WriteLine(item);
            }
            //Console.WriteLine();
            Console.ReadKey();
        }


        /// <summary>
        /// 找规律法，确实找出来了，(一开始用try法，超出限制，后改成其他方法，通过)：try耗时
        /// </summary>
        /// <param name="mat"></param>
        /// <returns></returns>
        public static int[] FindDiagonalOrder(int[][] mat)
        {
            List<int> list = new List<int>();
            int size = mat.Length > mat[0].Length ? mat.Length * 2 - 1 : mat[0].Length * 2 - 1;

            //int moreBig = mat[0].Length > mat.Length ? mat[0].Length : mat.Length;
            bool isX = mat[0].Length > mat.Length ? true : false;
            int line = isX ? mat[0].Length - 1 : mat.Length - 1;
            for (int i = 0; i < size; i++)
            {
                if (i < line+1)
                {
                    if (i % 2 == 0)
                    {
                        //偶数
                        for (int j = i; j >= 0; j--)
                        {
                            if (j>= mat.Length || (j < mat.Length&&(i - j)>= mat[j].Length))
                            {
                                continue;
                            }
                            list.Add(mat[j][i - j]);
                        }
                    }
                    else
                    {
                        for (int j = 0; j <= i; j++)
                        {
                            if (j >= mat.Length || (j < mat.Length && (i - j) >= mat[j].Length))
                            {
                                continue;
                            }
                            list.Add(mat[j][i - j]);
                        }
                    }
                }
                else
                {
                    if (i % 2 == 0)
                    {
                        //偶数
                        for (int j = line; j >= (line) - (size - i); j--)
                        {
                            if (j >= mat.Length || (j < mat.Length && (i - j) >= mat[j].Length))
                            {
                                continue;
                            }
                            list.Add(mat[j][i - j]);
                        }
                    }
                    else
                    {
                        for (int j = (line) - (size - i) + 1; j <= line; j++)
                        {
                            if (j >= mat.Length || (j < mat.Length && (i - j) >= mat[j].Length))
                            {
                                continue;
                            }
                            list.Add(mat[j][i - j]);
                        }
                    }
                }
            }
            return list.ToArray(); 
            //00 
            //01 10 
            //20 11 02 
            //12 21 
            //22


            //4*3
            //00                  0
            //01 10               1
            //20 11 02            2
            //03 12 21 //30       3
            ///*31*/ 22 13        4
            //23 /*32*/           5
            ////33                6
            ///

            //3*4
            //00
            //01 10
            //20 11 02
            ///*03*/ 12 21 30
            //31 22 13

        }
    }
}
